1. Field of the Invention
The invention relates to memories, and more particularly to flash memories.
2. Description of the Related Art
A flash memory comprises a plurality of blocks. Each block comprises a plurality of pages for data storage. Each block also maps to a unique address. When a host wants to access data stored in the flash memory, the host sends an access command to a controller of the flash memory, wherein the access command comprises an address of the block storing the data to be accessed. The controller then accesses data from the flash memory according to the address. For example, when the flash memory receives a write command from the controller, the flash memory writes data to the block corresponding to the address. When the flash memory receives a read command from the controller, the flash memory reads data from the block corresponding to the address and sends the read data back to the controller.
After data is written to all pages of a block of a flash memory, other data cannot be written to the block again. A plurality of blocks of a flash memory is therefore divided into data blocks of a data area and spare blocks of a spare area. Data blocks of the data area have stored data, and spare blocks of the spare area have no stored data. When the host wants to write data into a write address corresponding to a data block of the data area, because update data cannot be written to the data block again, the controller obtains a spare block from the spare area, changes the address of the spare block to the write address, and then writes the update data to the spare block. Because the data block originally mapped to the write address is useless, the controller erases data from the data block to convert the data block to a spare block.
Ordinarily, when a controller selects a spare block from the spare area, a first-in first-out (FIFO) method is used to select the spare block. In other words, the controller selects a spare block with the earliest erase time index in comparison with those of other spare blocks from the spare area. Referring to FIG. 2, a flowchart of a conventional data writing method 200 is shown. First, the controller receives a write command from a host (step 202). Assume that the write command requests the controller to write a write data to a first data block of the flash memory. Because the first data block has stored data, the controller cannot write the write data to the first data block. The controller therefore must obtain a target spare block for storing the write data in place of the first data block from the spare area of the flash memory. According to the first-in first-out method, the controller selects a first spare block with the earliest erase time index from the spare blocks of the spare area of the flash memory (step 204). The controller then takes the first spare block as the target spare block to hold the write data (step 206), and then controls the flash memory to write the write data to the target spare block (step 208). The target spare block therefore becomes a data block holding the write data in place of the first data block. The first data block holds old-version data and is useless. The controller therefore erases the old-version data from the first data block to convert the first data block to a spare block (step 210).
Referring to FIGS. 1A-1C, schematic diagrams of an embodiment of a conventional data writing method are shown. As shown in FIG. 1A, a data area 110 comprises data blocks 111, 112, 11K, 11P, 11Y, and 11Z which respectively have erase counts of 3, 5, 15, 6, 17, and 10. The spare area 120 comprises spare blocks 121, 122, 123, 124, and 12X which respectively have erase counts of 12, 11, 30, 7, and 9. Assume that a controller receives a write command for writing update data to the data block 11K of the data area 110. Because the update data cannot be written to the data block 11K which has stored data, the controller selects a spare block 121 with the earliest erase time index from the spare area 120 to hold the update data in place of the data block 11K. After the spare block 121 stores the update data, the spare block 121 is moved to the data area 110, as shown in FIG. 1B. Data is then erased from the data block 11K, wherein the erase count of the data block 11K is increased from 15 to 16, and the data block 11K having no data stored therein is then moved to the spare area 120, as shown in FIG. 1B. Assume that the controller further receives a write command for writing second update data to the data block 11P of the data area 110. Because the second update data cannot be written to the data block 11P which has stored data, the controller selects a spare block 122 with the earliest erase time index from the spare area 120 to hold the second update data in place of the data block 11P. After the spare block 122 stores the second update data, the spare block 122 is moved to the data area 110, as shown in FIG. 1C. Data is then erased from the data block 11P, wherein the erase count of the data block 11P is increased from 6 to 7, and the data block 11P having no data stored therein is then moved to the spare area 120, as shown in FIG. 1C.
The conventional data writing method 200 shown in FIG. 2, however, has a deficiency. Because the controller selects the target spare block for holding update data from the spare area according to only the first-in first-out method (step 204), the controller may obtain a target spare block with a high erase count. When the target spare block with a high erase count is used to store update data, wherein the erase count of the target spare block is rapidly increased, the risk of over-wearing the target spare block is increased. Referring to FIGS. 3A and 3B, schematic diagrams of an embodiment of over-wearing of blocks according to a conventional data writing method are shown. In FIG. 3A, assume that the controller receives a writing command for writing update data to a data block 111 of a data area 110. Because the update data cannot be written to the data block 111 which has stored data, the controller selects a spare block 123 with the earliest erase time index from the spare area 120 to hold the update data in place of the data block 111. After the spare block 123 stores the update data, the spare block 123 is moved to the data area 110, as shown in FIG. 3B. Data is then erased from the data block 111, wherein the erase count of the data block 111 is increased from 3 to 4, and the data block 111 having no data stored therein is then moved to the spare area 120, as shown in FIG. 3B. The block 123 with a high erase count of 30 is still used to store update data. When data is erased from the block 123 again, wherein the erase count of the block 123 is further increased to 31, and a risk of identifying the block 123 as a worn-out block is increased. To solve the aforementioned problem, a new data writing method is required.